package Hot100;

/**
 * @author zhangmin
 * @create 2021-12-28 10:40
 *
 * 买卖股票问题：
 * 泛型：给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 *
 * 121. 买卖股票的最佳时机--k=1
 * 122. 买卖股票的最佳时机 II--k=+infinity（正无穷）
 * 123. 买卖股票的最佳时机 III--k=2
 * 188. 买卖股票的最佳时机 IV--标准泛型
 * 309. 最佳买卖股票时机含冷冻期--k=+infinity（正无穷）,包含冷冻期=1
 * 714. 买卖股票的最佳时机含手续费--k=+infinity（正无穷）,包含手续费=fee
 *
 * 思路：
 * 「状态」有三个：一、是天数，二、是允许交易的最大次数，三、是当前的持有状态（即 rest 的状态，我们不妨用 1 表示持有，0 表示没有持有）
 * dp[i][k][0 or 1]表示第i天手里持有股票（或不持有，0,1）至少进行k次交易的最大收益。
 * 求的最终答案是 dp[n - 1][K][0]，即最后一天，最多允许 K 次交易，最多获得多少利润。
 * dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
 *               昨天就没有持有，且截至昨天最大交易次数限制为 k，今天选择保持，最大交易次数限制依然为 k。
 *               昨天持有股票，且截至昨天最大交易次数限制为 k，今天选择卖出，所以我今天没有持有股票了，最大交易次数限制依然为 k。
 * dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
 *               昨天就持有着股票，且截至昨天最大交易次数限制为 k；然后今天选择 保持，所以我今天还持有着股票，最大交易次数限制依然为 k
 *               昨天本没有持有，且截至昨天最大交易次数限制为 k - 1；但今天我选择 买入，所以今天我就持有股票了，最大交易次数限制为 k。
 * dp[-1][...][0] = 0   因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0。
 * dp[-1][...][1] = -infinity    还没开始的时候，是不可能持有股票的。
 * dp[...][0][0] = 0    因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0。
 * dp[...][0][1] = -infinity   不允许交易的情况下，是不可能持有股票的。
 */
public class maxProfit121 {
    /**
     * 121. 买卖股票的最佳时机
     * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
     * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
     * dp:先计算相邻两天的差值，然后对差值进行最大子数组的求解即可
     * dp[i]表示以第i天为结尾的最大子数组的和,dp[i]=Math.max(dp[i-1]+dif[i],dif[i])
     * */
    public int maxProfit1(int[] prices) {
        int n=prices.length;
        if (n==1)return 0;
        int[] dif=new int[n];
        dif[0]=0;
        for (int i = 1; i < n; i++) {
            dif[i]=prices[i]-prices[i-1];
        }
        int dp_1=dif[0];
        int res=0;
        for (int i = 1; i < n; i++) {
            int dp=Math.max(dp_1+dif[i],dif[i]);
            dp_1=dp;
            res=Math.max(res,dp);
        }
        return res;
    }

    /** 121--套框架
     * k=1，舍去k状态
     * dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
     * dp[i][1] = max(dp[i-1][1], -prices[i])
     * */
    public int maxProfit2(int[] prices) {
        int n=prices.length;
        int[][] dp=new int[n][2];
        for (int i = 0; i < n; i++) {
            if (i==0){
                dp[i][0]=0;
                dp[i][1]=-prices[i];
                continue;
            }
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],-prices[i]);
        }
        return dp[n-1][0];
    }

    /**
     * 122. 买卖股票的最佳时机 II---k=正无穷
     * 给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
     * 思路：k为正无穷，可以认为k和k-1是一样的
     * dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
     * dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
     * */
    public int maxProfit3(int[] prices) {
        int n=prices.length;
        int[][] dp=new int[n][2];
        for (int i = 0; i < n; i++) {
            if (i==0){
                dp[i][0]=0;
                dp[i][1]=-prices[i];
                continue;
            }
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        return dp[n-1][0];
    }

    /**
     * 123. 买卖股票的最佳时机 III----k=2
     * 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
     * dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
     * dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
     * */
    public int maxProfit4(int[] prices) {
        int max_k=2,n=prices.length;
        int[][][] dp=new int[n][max_k+1][2];
        for (int i = 0; i < n; i++) {
            for (int k = max_k; k >=1; k--) {
                if (i==0){
                    dp[i][k][0]=0;
                    dp[i][k][1]=-prices[i];
                    continue;
                }
                dp[i][k][0]=Math.max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);
                dp[i][k][1]=Math.max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]);
            }
        }
        return dp[n-1][max_k][0];
    }

    /**
     * 188. 买卖股票的最佳时机 IV ---k=k
     * 给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
     * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
     * */
    public int maxProfit5(int k, int[] prices) {
        int n=prices.length;
        if (n<=0) return 0;
        if (k>n/2) {
            //能交易的次数超出了数组本身可以交易的次数，次数不受限制
            return maxProfit3(prices);
        }
        int[][][] dp=new int[n][k+1][2];
        for (int i = 0; i < n; i++) {
            //k为0时，base case
            dp[i][0][1]=Integer.MIN_VALUE;
            dp[i][0][0]=0;
            continue;
        }
        for (int i = 0; i < n; i++) {
            for (int j = k; j >=1 ; j--) {
                if (i==0){
                    dp[i][j][0]=0;
                    dp[i][j][1]=-prices[i];
                }
                dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);
                dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);
            }
        }
        return dp[n-1][k][0];
    }


    /**
     * 309. 最佳买卖股票时机含冷冻期
     * 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
     * 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
     * 改造第三个：
     * dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
     * dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
     * */
    public int maxProfit6(int[] prices) {
        int n=prices.length;
        int[][] dp=new int[n][2];
        for (int i = 0; i < n; i++) {
            if (i==0){
                dp[i][0]=0;
                dp[i][1]=-prices[i];
                continue;
            }
            if (i==1){
                dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
                dp[i][1]=Math.max(dp[i-1][1],-prices[i]);
                continue;
            }
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-2][0]-prices[i]);
        }
        return dp[n-1][0];
    }

    /**
     * 714. 买卖股票的最佳时机含手续费
     * 给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
     * 你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。
     * 思路：在3的基础上修改，相当于买入的价格比之前贵了
     * dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
     * dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee)
     * */
    public int maxProfit(int[] prices, int fee) {
        int n=prices.length;
        int[][] dp=new int[n][2];
        for (int i = 0; i < n; i++) {
            if (i==0){
                dp[i][0]=0;
                dp[i][1]=-prices[i]-fee;
                continue;
            }
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]-fee);
        }
        return dp[n-1][0];
    }
}
